The present invention relates to computer programming and data storage and transmission methods, as well as to user interface methods.
Handheld computers (also known as xe2x80x9cpalmsxe2x80x9d or xe2x80x9cpalmtopsxe2x80x9d are increasing in popularity. They are small, light, and can do many desired tasks without the user having to carry, boot-up, charge, etc. a laptop of other computer-type alternative.
A serious limitation of all palmtops relates to their capacity to store information. Palmtops lack hard drives, and must store whatever information is to be stored in hardware memory. Memory can be expanded only to a finite degree without sacrificing the very size and weight characteristics for which palmtops were designed, and nothing resembling hard drives, as such, is likely to be found in palmtops in the foreseeable future.
The only material way in which the capabilities for palmtops to manage larger volumes of information in the foreseeable future is through manipulation and management of the information itself, not through changes in the architecture of the palmtops.
The present invention presents a programming and data management methodology which greatly advances the capacity of a palmtop to retrieve and process information to a magnitude far beyond any comparable quantitative level as might be achieved through use of prior art data management methods, or through reasonable changes in palmtop construction.
As will be discussed below in considerable detail, properly allocating data gathering and data processing and interpretation tasks between a palmtop and a central computing unit increases a palmtop""s capacity to prompt a user in providing, and then retrieve and store information for later processing in volumes far in excess of that possible with a palmtop""s present capabilities while using present art data management and programming regimens.
The current state-of-the-art for remote user-interface generation and reporting is the hypertext markup language or xe2x80x9cHTMLxe2x80x9d. This system differs in lacking the data distillation aspect. This weakness is manifested in several ways:
1) When the script is transferred to the remote computer, the entire script is transferred, placing a greater burden on the bandwidth and storage requirements of the remote system.
2) The remote computer must deal with the original HTML document, which requires it to parse and process enormous amounts of data irrelevant to the purpose of user interface generation.
3) When a data record or xe2x80x9cformxe2x80x9d is returned from the remote site, field identifiers are attached to each field individually, vastly increasing the bandwidth requirement of the interaction. In the present system, data can be identified by it""s position within a highly compacted data record, eliminating the need to transfer the id tags.
4) HTML does not provide a platform-independent binary representation of the user interface. This requires extensive parsing functions to be provided by the system used to display the interface. The present distillation process can produce, as one aspect of the document, a binary representation that can be used on any computer.
5) The automatic generation of a hierarchical representation when distilling the script for the user interface process eliminates the xe2x80x9cinfinite mazexe2x80x9d problem found in conventional hypertext systems, where the xe2x80x9cforward/backxe2x80x9d paradigm commonly used does not give the user a clear mental image of the organization of the document.
Another language to be discussed in the data management realm is XML (extensible markup language). XML allows the development of custom tags, but does not contain the concept of distillation/expansion contained in the present invention. In fact, XML could be used as the underlying scripting language in a document distillation system. XML also differs conceptually in that it provides a document TYPE definition rather than a document INSTANCE definition. In other words, XML document processors refer to a template that describes in general terms the meaning of custom tags in the language, while a processor that operates on one of the distilled data records employed in the present methodology may also refer to the original document itself, which provides much more flexible and powerful processing capabilities, as well as the extreme data density allowed by the distillation process.
Conventional data compression techniques fall into two classes, xe2x80x9closslessxe2x80x9d and xe2x80x9clossyxe2x80x9d. An example of a lossy mechanism is that employed by conventional JPEG image files on the internet. Compression ratios in the range 50 or 100 to 1 are common, but at the expense of imperfect reconstruction of the original image. This is considered an acceptable tradeoff given the desire for rapid downloading of images.
In transferring data such as text, or selections from checkboxes on a user interface, clearly lossless compression is necessary. Lossless compression algorithms such as Lempel-Ziv-Welch (LZW) compression or Huffman encoding typically produce compression ratios on the order of two-to-one, depending on the type of data.
Consider a hypothetical example of a survey form consisting of 1000 checkboxes each with a twelve-character idtag as required by a conventional html system (the number twelve is an arbitrary but conservative estimate of the size of a typical field idtag, most programmers use xe2x80x9csymbolsxe2x80x9d this large or larger). The data required for a single record by the conventional system would be at least (assuming no other formatting overhead and that the state of each checkbox is transmitted as a single byte of data):
1000*12+1000*1=13000 bytes.
According to the present methodology, the data required is 4 bytes for the tag required to identify the original script, plus 1 bit per checkbox:
4+1000/8=129 bytes.
This yields an effective compression ratio of:
13000/129=100.77
Note that conventional compression schemes may be applied xe2x80x9con top ofxe2x80x9d the data representations employed by the subject methodology, thereby resulting in further reductions.
Concerning external data representation, computer platforms differ in their binary format for representing data. For example, in many palmtop computers integers are stored using most-significant-byte-first format, whereas on standard PC platforms integers are stored in a least-significant-byte first format. The byte ordering must be reversed for data generated on one platform before it may be utilized on computers of the other platform.
In conventional systems such as the xe2x80x9cremote procedure callxe2x80x9d (RPC) system and the xe2x80x9csocketsxe2x80x9d system, which move data between different computer platforms, the process involves two stages of data translation into an intermediate xe2x80x9cexternalxe2x80x9d data representation, with the associated overhead. This intermediate representation may be binary or text-based, but always requires two translation layers.
According to the present invention, data is stored in the native format of the xe2x80x9clow poweredxe2x80x9d system and is transformed only at the time of use. There is no wasted format translation, and no translation at all is required of the less capable platform.
Consider the following comparison between conventional inter-platform exchange and data exchange in accordance with the present invention:
Conventional Inter-platform Exchange.
Data entered on mobile system in native format
All data translated to xe2x80x9cportablexe2x80x9d format
Data sent to host computer
All data translated to host format
Some data accessed and used by host
The Current Invention""s Inter-platform Exchange.
Data entered on mobile system in native format
Data sent to host system.
Data translated to host format only as required.
In what follows, note that the present techniques are not specific to the script syntax given as examples. In principle the present distillation mechanisms could be applied to industry-standard HTML, XML, or scripts based on other commonly used languages.
The methodologies of the present invention solve several problems associated with software development in general and mobile computing in particular:
Optimal use of limited bandwidth. The very-efficient data storage strategies of the present invention methodologies allow handheld computers with low data rate connections to transfer huge amounts of data. Today a central problem in practical computer usage is the ability to transfer information between networked computers. In desktop computers it is now common for home computers to have multi-megabit data rate connections to the internet through cable modems or other so-called xe2x80x9cbroadbandxe2x80x9d technologies. Palmtop computers are severely limited in their communications bandwidth, often operating over wireless connections at data rates of 9600 bps (bits per second) or even lower. This is a serious obstacle to the deployment of palmtop computers in remote data gathering applications.
Traditional data compression techniques cannot achieve compression ratios of greater than about two-to-one without loss of data. Higher ratios are possible for image data, but only in the case where image degradation through imperfect reconstruction is acceptable. Such popular image formats as xe2x80x9cjpegxe2x80x9d use such techniques, but such xe2x80x9clossyxe2x80x9d mechanisms are not applicable to transmission of binary data records of the type required by remote data collection applications.
Optimal use of limited memory and processing power on mobile and hand-held computer platforms. The xe2x80x9cdistilledxe2x80x9d data records and documents of the present invention allow software applications with unprecedented levels of complexity to be stored and displayed rapidly on handheld computers with extremely limited processing power and memory.
By removing information from the script that is irrelevant to the user-interface process, the parsing of the script is simplified on the handheld computer, giving its users operational capabilities far in excess of that now possible with present day data management and structure, and presently otherwise possible only with vastly increased computing power. Many of the handheld computers often are entirely without the disk storage that is taken for granted on most desk top computers. In these devices all data records must be stored in small non-volatile memories, which are extremely limited in size. While a conventional word processing application may be able to use a megabyte of data for a simple document, handheld applications have no such luxury.
By completely separating the xe2x80x9cmeaningxe2x80x9d of the data from the data itself, one achieves very high xe2x80x9cinformation densityxe2x80x9d, making it possible to store large numbers of data records in even the limited memory of a diskless handheld computer.
Enhanced software productivity. The new document types involved in the present invention allow a non-technical user, generally a xe2x80x9cdomain expertxe2x80x9d or expert in the subject matter, to create the content, data flow, storage elements, and screen elements without the need for programmer involvement. This enables true software development by people with NO software background, and in fact even those with marginal computer literacy skills.
Enhanced ability to capture expert knowledge and user Requirements. The knowledge-capture process is a perennial block to productivity in the software realm. The presently described new document types allow the domain expert to perform his or her own knowledge capture without programmer involvement. Given the script which defines the data elements which the content developer wishes to capture, the present combined distillation/expansion processes automatically perform user-interface creation, allocation of data storage, and report generation. The domain expert is therefore required only to specify the problem, the solution is generated automatically.
The syntax of the scripting language used is not critical to the process. An example is given here, which emphasizes a plain-English syntax to enhance readability. Such a language has in fact been used directly by non-technical users with brief training. Simple authoring tools based on the well known RAD (rapid application development) paradigm are also possible to further simplify script creation.
Ability to navigate very large amounts of data easily. xe2x80x9cInformation overloadxe2x80x9d is a serious problem with current computing paradigms. The ability of the present documents to automatically specify a hierarchical representation, and to specify filters which suppress irrelevant information, allow a user to navigate an unprecedented quantity of data in an extremely fast and efficient manner.
This problem of information overload and document navigation is particularly severe in the handheld arena, where display sizes are very limited. The hierarchy of display and filtering capabilities are essential to making practical the extraordinarily complex applications that are and will be required on handheld computers.
Well-defined separation of client-side and server-side workload. In the present system, the different distillations clearly delineate the purposes and responsibilities of different subsystems: The handheld component (the xe2x80x9cinformation retrieval computerxe2x80x9d), who""s advantage is mobility and simplicity, is responsible for acquiring and transmitting data. The xe2x80x9chostxe2x80x9d or xe2x80x9cserverxe2x80x9d component (the xe2x80x9cdata processing computerxe2x80x9d), is responsible for associating data records with the original scripts, and for performing processing that is beyond the scope of the handheld system.
In what follows, the new document type involved in practice of the present invention will be a xe2x80x9cscriptxe2x80x9d. A script defines a set of data fields as well as a hierarchy of organization. A script consists of token-value pairs. The specific tokens used here are not important, and in fact other tokens are substituted in some implementations.
The exact syntax of the script is likewise irrelevant. The token=value syntax presented here is only one possible implementation.
Script aspects. A key element of the script is the specification of multiple xe2x80x9caspectsxe2x80x9d of the problem in a way that can be xe2x80x9cdistilledxe2x80x9d so that different users or computer systems need only deal with those aspects that concern them, and yet the different aspects may still interact when the results of different processes are combined by the expansion apparatus. Described in more detail below are some possible aspects, which are among those used in the present invention""s experimental implementation:
The data field aspect
The representation hierarchy aspect
The contextual Filter aspect
The data processing aspect
The data position aspect
The field-idtag aspect
The user-defined aspect
The constraint aspect
The page-layout aspect
Clearly other aspects are possible. The accompanying sample script illustrates some possible aspects including the ones mentioned here.
The data field aspect. This aspect allows the specification of individual data-entry fields, which may be simple or complex and have an associated data type.
A simple example is a checkbox:
BEGIN FIELD
FIELD TYPE=checkbox
LABEL=cardio pulmonary arrest
END FIELD
This script specifies that one wishes to create a checkbox and to label the checkbox xe2x80x9ccardio pulmonary arrestxe2x80x9d. This is the most primitive aspect, which is combined with other script aspects to provide the significant benefits of the present invention.
The representation hierarchy aspect. The script defines a hierarchy of representation for the data, allowing the building of user interfaces using a shallow-tree hierarchy. This is done by defining sections and subsections within the script, which can then be used by a distillation device to produce a navigation hierarchy. One example of a syntax which accomplishes this is as follows:
BEGIN SECTION=(section 1 name)
BEGIN SUBSECTION=(subsection 1.1 name)
BEGIN FIELD
. . .
END FIELD
END SUBSECTION
BEGIN SUBSECTION=subsection 1.2 name
BEGIN FIELD
. . .
END FIELD
END SUBSECTION
END SECTION
BEGIN SECTION=(section 2 name)
. . .
END SECTION
For example, in a palm computer implementation developed according to the subject invention, the end product allows up to 20 script sections with 20 subsections per section. This allows a user, with only two pen taps on a mobile computer with a very limited display, to access 400 different subsections of a computer application. Each of these subsections may contain an arbitrary number of fields which can then be found using page-forward/page-back commands much like a conventional book or multi-page form.
This hierarchy may be extended by the nesting of fields:
BEGIN FIELD
FIELD TYPE=checkbox
. . .
BEGIN FIELD
FIELD TYPE=popup list
. . .
END FIELD
END FIELD
In this manner, by enabling fields to be contained within other fields and only displayed when xe2x80x9ctriggeredxe2x80x9d by use of the enclosing fields, the hierarchy may be extended to whatever depth required.
The contextual filter aspect. To further enable the navigation of extremely large data sets with very limited computer resources and limited display sizes, scripts allow the definition of xe2x80x9ctopicsxe2x80x9d, xe2x80x9cdetail levelsxe2x80x9d, and other filtering mechanisms which can enable the display apparatus to selectively limit the display of data fields.
For example, envision a medical application in which one wishes to display certain fields only if the user""s patient is suffering from a particular problem. One can then specify topics in the script . . .
BEGIN TOPIC DEFINITIONS
BEGIN TOPIC
TOPIC IDTAG=Major Burn
END TOPIC
BEGIN TOPIC
TOPIC IDTAG=Chest Pain
END TOPIC
END TOPIC DEFINITIONS
One can then specify that the following field is only relevant for the xe2x80x9cBurnxe2x80x9d topic:
BEGIN FIELD
FIELD TYPE=checkbox
LABEL=smoke inhalation
TOPIC=Major Burn
END FIELD
Now the distillation apparatus may, at the time the field is presented, choose to display or not display each field based on the current context. The value of this filtering mechanism is greatly enhanced by the distillation process, which creates a new version of the script in which the enable status of each field is encoded in a single bit for each topic. This distilled version is delivered to the user-interface process, which thus is not required to perform the computationally-intensive parsing operations that would be required by prior-art script processing systems in order to determine the run-time form of the user interface.
Other contextual filters are possible and have been implemented. For example, the following field is only relevant for females in a certain age range. Note the SEX and AGE filters which are now included in the field . . .
BEGIN FIELD
FIELD TYPE=yesno
LABEL=home pregnancy test used
SEX=female
MIN AGE YEARS=10
MAX AGE YEARS=55
END FIELD
The data processing aspect. Data records produced using the script will in general be used for some type of analysis or reporting. Two examples are a printing process and an invoice-generation process.
Suppose, for example, we have an automatic printing process which composes text based on the labels within a field. Suppose further that we have a xe2x80x9cyes/noxe2x80x9d control type where we wish to print a specific format in the xe2x80x9cnoxe2x80x9d case. We might then use a xe2x80x9cprint controlxe2x80x9d aspect to override the default printing logic:
BEGIN FIELD
FIELD TYPE=yesno
LABEL=remembers traumatic event
PRINTCON IFNO PRINT=does not remember
traumatic event
END FIELD
Consider a second example where an invoice generation process is used to automatically produce items based on the content of a distilled data record. To the user interface, this process is irrelevant, while to the billing process it is crucial. In the following field, we have used a BILLING CODE directive as an example of a data-processing aspect . . .
BEGIN FIELD
FIELD TYPE=yesno
LABEL=Patient defibrillated
BILLING CODE=12345
END FIELD
Clearly other such processing aspects are possible.
The data Position aspect. This aspect of the data is implicit within the script and depends on the simple observation that each field has a specific position within the overall script. The fields can simply be numbered from 1 to xe2x80x9cNxe2x80x9d where xe2x80x9cNxe2x80x9d is the total number of fields within the script. While seemingly trivial, this fact implies the ability to obtain the very efficient data storage described below.
The field-idtag aspect. This aspect allows any field in the system to be xe2x80x9ctaggedxe2x80x9d with a symbol, which may be used to identify the field unambiguously from another field or to provide special processing for that field. For example, suppose that we wish to present the same data field in two different locations in the same user interface. The first field in the following example creates a checkbox. The second takes advantage of the field idtag aspect to create a duplicate field, which will be slaved to the same database information and present the same label. Note also that other aspects of the field, such as the conditions under which it will be enabled, may be over-ridden by the duplicate field:
BEGIN FIELD
FIELD TYPE=checkbox
LABEL=normal HEENT exam
PRINTCON USERDEFINED
FIELD IDTAG=normal HEENT exam
END FIELD
.
.
.
BEGIN FIELD
DUPLICATE=normal HEENT exam
DEFAULT DLEVEL2
END FIELD
Another use of the field idtag is to provide customized or non-standard processing for an individual field. One such example is outlined in the section discussing the xe2x80x9cuser-definedxe2x80x9d aspect.
Note that field idtags may either be generated by hand, or be automatically generated by a script processing stage. Automated authoring tools may be used to guarantee that the idtags are unique and persistent across script revisions, so that custom processing will not be lost or disrupted when the script is edited.
In conventional script and computer language processing, the idtag concept is embodied as a xe2x80x9csymbol tablexe2x80x9d. These are usually based on hashing or tree algorithms which require operating system support for large dynamic memory structures and look-up algorithms. In the present implementation, when the distillation process generates a version of the script for use in data storage or user interface generation, we may use the data position aspect to replace the idtag with a simple numeric index, which allows inter-field references to be no more complex than array references. This makes idtags practical in a resource-constrained system such as a handheld computer.
The user-defined aspect.
Consider the following field definition:
BEGIN FIELD
FIELD TYPE=checkbox
LABEL=normal HEENT exam
PRINTCON USERDEFINED
FIELD IDTAG=normal HEENT exam
END FIELD
Note the xe2x80x9cPRINTCON USERDEFINEDxe2x80x9d tag. This informs the system that when this data is printed, the text to be printed is to be taken from a file generated by the user and associated with this field using the FIELD IDTAG. In the case where different users desire different custom processing, a separate file of user definitions is associated with every handheld device, and within that file field idtags are used to identify the fields to which custom processing applies. In this way the processing of the script may be completely customized on a per-user basis. The distilled data record need only be transmitted with some identifier specifying the originator, and the processing modified accordingly by the server-based data processing.
The constraint aspect. It is useful in many user interfaces to build in xe2x80x9cconstraintsxe2x80x9d on the data that may be entered, such as ranges on the data or inter-field constraints on data items that are mutually exclusive. An example is a set of checkboxes which are mutually exclusive, conventionally known as xe2x80x9cradio buttonsxe2x80x9d. This constraint may be applied by a xe2x80x9cgroup identifier syntaxxe2x80x9d such as the following:
CREATE AUTO GROUP ID
BEGIN FIELD
FIELD TYPE=checkbox
LABEL=Patient arrived via ambulance.
GROUP ID=auto
END FIELD
BEGIN FIELD
LABEL=Patient was brought in by parents
GROUP ID=auto
END FIELD
Clearly other such constraints are possible.
The page layout aspect. In general a distillation apparatus can produce a user interface using only the hierarchy and field definitions. However, one aspect of the script allows us to override this automatic mechanism with tokens that give explicit xe2x80x9chintsxe2x80x9d or xe2x80x9cdirectivesxe2x80x9d to the distillation apparatus. For example, if we wish two fields to appear side-by-side on the display where the automatic user interface generation would normally place the second field on a new line, we might write as follows (note the SUPPRESS LINEFEED directive)
BEGIN FIELD
FIELD TYPE=checkbox
LABEL=Fever
END FIELD
BEGIN FIELD
FIELD TYPE=checkbox
LABEL=Sore Throat
SUPPRESS LINEFEED
END FIELD
Clearly other such directives are possible to selectively override aspects of the automatic generation of user interfaces.